def plan(E: list[int]) -> int:
    dp1, dp2 = 0, 0
    for x in E:
        dp1, dp2 = max(dp1, x + dp2), dp1
    return dp1
 
def plan1(E: list[int]) -> int:

    # dp[i]表示从E[0..i]中取得的最大收益
    n = len(E)
    dp = [0] * n

    for i in range(n):
        # 分支1：第i天不出行，所以收益为0，总收益跟之前一样
        if (i > 0): # 代码细节：不加这个判断下一句有可能数组越界
            dp[i] = dp[i - 1]

        # 分支2：当天出行，这样前一天E[i-1]就不能出行，总收益加上dp[i-2]
        money = E[i]
        if (i >= 2): 
            money += dp[i - 2]
        if (money > dp[i]): 
            dp[i] = money 

    # 备忘录的最后一个值为答案
    return dp[-1]

# main
E = [ 7, 9, 7, 1, 6, 8, 3, 4 ]
result = plan(E)
print('最大收益:', result)



